UVA12177 First Knight

发布于 2020-09-05 | 分类于期望dp 、高斯消元 | 4分钟 | 580字数

设 $dp(i,j)$ 表示由 $(i,j)$ 走到 $(n,m)$ 的期望步数。

那么显然有转移：

dp(i,j)=1+(up(i,j) \times dp(i+1,j) + down(i,j) \times dp(i-1,j) + left(i,j) \times dp(i,j-1) + right(i,j) \times dp(i,j+1))

CF685B Kay and Snowflake

发布于 2020-09-05 | 分类于重心、倍增 | 2分钟 | 388字数

这道题应该算是

\text{CSP2019 树的重心}

的前置知识了吧。~~可惜之前我并没有做过。~~

对于一棵以 $u$ 为根的子树，它的重心只可能在点 $u$ 或以点 $u$ 的重儿子为根的子树中。

那么类比 $\text{lca}$ 倍增父亲，树的重心倍增重儿子。

发布于 2020-09-05 | 分类于树形dp | 3分钟 | 487字数

$n$ 个点 $m$ 条边的无向无环图，其实就是一个森林。

题目要求最小化两个量：灯数和只被一边照亮的边数。

一个做法是定义两个 $dp$ 数组，分别表示最小灯数和在灯数最小情况下的一边被照亮的最小边数。

发布于 2020-09-05 | 分类于数位dp | 2分钟 | 324字数

首先有个想法，如果该位为 $0$ 且不是前导 $0$ ，则将 $0$ 的数量加一，最后看 $0$ 是否出现了至少 $\lceil \frac{\text{len}}{2} \rceil$ 次。

但这样有个问题，比如在 $n=8(1000)_2$ 时， $2(0010)$ 就不会被计入答案，原因是 $2$ 的前导 $0$ 也算在了它二进制的位数中。

所以还要记录前导零的数量 $\text{leadnum}$ ，最后判断是否出现至少 $\lceil \frac{\text{len}-\text{leadnum}}{2} \rceil$ 即可。

发布于 2020-09-05 | 分类于数位dp | 2分钟 | 304字数

每个数的数字和的和其实就是所有数字与它出现次数的积的和。

那么对于 $0-9$ ，依次像 P2602 [ZJOI2010]数字计数统计出现次数就可以了。

具体做法也很简单，记录前 $pos$ 位某个数字出现次数 $sum$ ，记忆化搜索即可通过。

发布于 2020-09-05 | 分类于生成函数 | 4分钟 | 551字数

设整数 $n$ 的 $\text{lqp}$ 拆分权值为 $g(n)$ , 那么有：

\begin{cases} g(n)=1 & (n=0) \\

发布于 2020-07-14 | 分类于莫比乌斯反演 | 6分钟 | 934字数

\sum_{i=1}^n\sum_{j=i+1}^n\text{lcm}(A_i,A_j)

\frac{\sum_{i=1}^n\sum_{j=1}^n\text{lcm}(A_i,A_j)-\sum_{i=1}^nA_i}{2}